﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FindStartAndEndIndex
{
    /// <summary>
    /// Given a sorted integer array and a number, find the start and end indexes of the number in the array. 
    /// 
    /// Complexity should be less than O(n)
    /// 
    /// http://www.careercup.com/question?id=20854663
    /// </summary>
    class Program
    {
        static void Main(string[] args)
        {
            int[] array1 = { 0, 0, 2, 3, 3, 3, 3, 4, 7, 7, 9 };
            int[] array2 = { 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 7 };
            int[] array3 = { 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 };

            int[] result1 = FindStartEndIndex(array3, 4);

            for (int i = 0; i < 2; i++)
            {
                Console.Write(" {0} ", result1[i]);
            }
            Console.WriteLine();

            int[] result2 = FindStartEndIndexOptimized(array3, 4);

            for (int i = 0; i < 2; i++)
            {
                Console.Write(" {0} ",result1[i]);
            }

            Console.WriteLine(BinarySearch(array1, 3, 0, array1.Length));
            Console.Read();
        }

        public static int[] FindStartEndIndex(int[] input, int key)
        {
            int[] result = { -1, -1 };

            int count = 0;

            bool flag = false;
            for (int i = 0; i < input.Length; i++)
            {
                if (input[i] == key)
                {
                    if (flag)
                    {
                        result[1] = i;
                    }
                    else
                    {
                        result[0] = i;
                        flag = true;
                    }
                }

                count++;
            }

            Console.WriteLine("Total Iterations:{0}", count);
            return result;
        }

        public static int[] FindStartEndIndexOptimized(int[] input, int key)
        {
            int[] result = {-1,-1};

            int i = 0;
            int j = input.Length-1;
            int count = 0;

            while (i<=j)
            {
                if (input[i] == key && result[0] != -1)
                    result[0] = i;

                if (input[j] == key && result[1] != -1)
                    result[1] = i;

                i++;
                j--;

                count++;
            }

            Console.WriteLine("Total Iterations:{0}", count);

            return result;
        }
       
        public static int BinarySearch(int[] input, int key, int min, int max)
        {
            int count = 0;

            while (max >= min)
            {
                Console.WriteLine(count++);

                int mid = min + ((max - min) / 2);

                if (input[mid] < key)
                {
                    min = mid + 1;
                }
                else if (input[mid] > key)
                    max = mid - 1;
                else
                    return mid;

            }
            
            return -1;
        }
    }
}
